package 中等.滑动窗口;

import java.util.*;

/**
 * 给你一个由 正 整数组成的数组 nums 。
 * 如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：
 * 子数组中 不同 元素的数目等于整个数组不同元素的数目。
 * 返回数组中 完全子数组 的数目。
 * 子数组 是数组中的一个连续非空序列。
 *
 * @ https://leetcode.cn/problems/count-complete-subarrays-in-an-array/description/
 * @date 2024/06/19
 */
public class 统计完全子数组的数目_2799 {

    public static void main(String[] args) {

    }

    /**
     * 滑动窗口+哈希表
     * 左端点固定，右端点向右移动，当窗口里面不同的元素等于整个数组不同的元素时
     * 停止移动，此时 [left,right-1至len-1] 都是完全子数组，可以贡献  len-right+1
     * 个完全子数组
     */
    public int countCompleteSubarrays(int[] nums) {
        int ans = 0;
        Set<Integer> totalSet = new HashSet<>();
        for (int num : nums) {
            totalSet.add(num);
        }
        Map<Integer, Integer> map = new HashMap<>();

        int left = 0, right = 0;
        while (left < nums.length) {

            while (right < nums.length && map.size() < totalSet.size()) {
                map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
                right++;
            }
            if (map.size() == totalSet.size()) {
                ans += nums.length - right + 1;
            }

            map.put(nums[left], map.get(nums[left]) - 1);
            if (map.get(nums[left]) <= 0) {
                map.remove(nums[left]);
            }
            left++;
        }

        return ans;
    }

}
